用 JavaScript 实现队列

发表于   |   分类于

队列和栈非常类似，但是使用了不同的原则，而非后进先出。

队列是遵循FIFO（First In First Out，先进先出， 也称先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

在现实中，最常见的例子就是排队：
Markdown

排在第一位的人会先接受服务。

创建队列

先从最基本的声明开始：

1
2
3
4
function Queue(){
    var items = [];
    // 添加属性和方法
}

接下来声明一些队列可用的方法：

  • enqueue(element(s)):向队列尾部添加一个（或多个）新的项；
  • dequeue():移除队列的第一（即排在队列最前面的）项，并返回被移除的元素；
  • front():返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动；
  • isEmpty():如果队列中不包含任何元素，返回true，否则返回false；
  • size():返回队列包含的元素个数。

下面是实现的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function Queue() {

    var items = [];

    this.enqueue = function(element){
        items.push(element);
    };

    this.dequeue = function(){
        return items.shift();
    };

    this.front = function(){
        return items[0];
    };

    this.isEmpty = function(){
        return items.length == 0;
    };

    this.clear = function(){
        items = [];
    };

    this.size = function(){
        return items.length;
    };

    this.print = function(){
        console.log(items.toString());
    };
}

优先队列

队列的一个修改版就是优先队列，即元素的添加和移除是基于优先级的。一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客优先级要高于经济舱乘客。

要实现一个优先队列，有两种选项：设置优先级，然后在正确的位置添加元素；或者用入列操作添加元素，然后按照优先级移除他们。

在这个例子中，我们将会在正确的位置添加元素，因此可以对它们使用默认的出列操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
function PriorityQueue() {

    var items = [];

    function QueueElement (element, priority){
        this.element = element;
        this.priority = priority;
    }

    this.enqueue = function(element, priority){
        var queueElement = new QueueElement(element, priority);

        if (this.isEmpty()){
            items.push(queueElement);
        } else {
            var added = false;
            for (var i=0; i<items.length; i++){
                if (queueElement.priority < items[i].priority){
                    items.splice(i,0,queueElement);
                    added = true;
                    break;
                }
            }
            if (!added){
                items.push(queueElement);
            }
        }
    };

    this.dequeue = function(){
        return items.shift();
    };

    this.front = function(){
        return items[0];
    };

    this.isEmpty = function(){
        return items.length == 0;
    };

    this.size = function(){
        return items.length;
    };

    this. print = function(){
        for (var i=0; i<items.length; i++){
            console.log(items[i].element + ' - ' + items[i].priority);
        }
    };
}

它的实现过程是这样的：如果队列为空，可以直接将元素入列。否则，就需要比较该元素与其他元素的优先级。当找到一个比要添加的元素的priority值更大（优先级更低）的项时，就把新元素插入到它之前。

例如：

1
2
3
4
5
var priorityQueue = new PriorityQueue();
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jack", 1);
priorityQueue.enqueue("Camila", 1);
priorityQueue.print();

过程如下：
Markdown

循环队列——击鼓传花

另一个修改版的队列实现，就是循环队列。循环队列的一个例子就是击鼓传花游戏。

在下面这个示例中，我们要实现一个模拟的击鼓传花游戏：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function hotPotato (nameList, num){

    var queue = new Queue();

    for (var i=0; i<nameList.length; i++){
        queue.enqueue(nameList[i]);
    }

    var eliminated = '';
    while (queue.size() > 1){
        for (var i=0; i<num; i++){
            queue.enqueue(queue.dequeue());
        }
        eliminated = queue.dequeue();
        console.log(eliminated + ' was eliminated from the Hot Potato game.');
    }

    return queue.dequeue();
}

var names = ['John','Jack','Camila','Ingrid','Carl'];
var winner = hotPotato(names, 7);
console.log('The winner is: ' + winner);

在这个函数中，我们输入一份名单，把里面的名字全部加入队列，再给定一个数字，然后迭代队列。

以上算法输出如下：

1
2
3
4
5
Camila was eliminated from the Hot Potato game.
Jack was eliminated from the Hot Potato game.
Carl was eliminated from the Hot Potato game.
Ingrid was eliminated from the Hot Potato game.
The winner is: John

下图模拟了这个输出过程：
Markdown

可以改变hotPotato函数的数字，模拟不同的场景。